iT邦幫忙

2021 iThome 鐵人賽

DAY 25
2

前言

如果昨天是資料結構,那今天必然是來討論演算法啦!

「演算法」是另一個會讓許多非本科系的 developer 嚇到的詞彙,會覺得好像是很高深難懂的技術,應該都是 Google 等級的程式設計師才會用到吧?

但很神奇的是,明明是看起來這麼難的一個詞彙,反而滿常出現在媒體用語中的:

所以今天讓我們來揭開演算法神秘的面紗吧!

跟昨天一樣,今天主軸在於讓大家初步認識演算法,沒有要帶著大家到處去刷題,如果有興趣想用演算法來實際解題,歡迎到我的隊友系列文,用 LeetCode 刷題來練習!

演算法是什麼?

由有限步驟所構成的集合,可以用於解決某一個特定的問題。

簡單來說,有點像是「解決某個問題的步驟流程」,比如在生活上,我們要做家事洗衣服:

  1. 把衣服放進洗衣袋
  2. 把洗衣袋及其他衣服都丟進洗衣機
  3. 放入洗衣精
  4. 打開洗衣機電源
  5. 選擇洗衣模式,按下啟動
  6. 完成

沒錯,上述五個步驟就是為了完成「洗衣服」這個任務,的其中一種演算法!那有沒有其它演算法?

有啊!衣服一定要自己洗嗎?

image alt

  1. 把衣服交給媽媽
  2. 完成

所以,要完成一件事情,演算法不只一種唷!

這只是個範例,衣服請自己洗嘿!

其實,「如何把大象放進冰箱裡」這個冷笑話,也是演算法的一種哦:

  1. 把冰箱門打開
  2. 把大象放進去
  3. 把冰箱門關上

是不是步驟非常明確,而且能夠解決問題呢XD

而在計算機科學的領域,演算法其實也是在做同樣的事情,我們透過設計一連串的指令、動作,讓電腦去執行,以便協助我們解決一些特定問題。

因此,就算是最簡單的:我想條列出商品名稱與對應的價錢,都是演算法的一種哦!

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
];

products.forEach(product => console.log(`${product.name} 的價錢是 ${product.price}`));

執行結果

TV 的價錢是 12000
laptop 的價錢是 25000
washing machine 的價錢是 8000

演算法有好壞之分嗎?

演算法其實就是「解決問題的方法」,所以這個問題應該改成:

解決問題的方法有好壞之分嗎?

嗯。。。聽起來是有的,只是我們不會說哪個方法絕對好,而是會用兩個指標來衡量:動用的資源以及花費的時間

而這兩個指標放在計算機科學領域,就是你曾經聽過的:

  • 動用的資源:空間複雜度
  • 花費的時間:時間複雜度

空間複雜度(Space Complexity)

空間複雜度就是,我用了多少記憶體空間來完成這件事。

比如要把一個陣列的順序完全反轉:

const reverseArr = (input) => {
    const output = [];
    input.forEach(item => output.unshift(item));
    console.log(output);
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

執行結果

[5, 4, 3, 2, 1]

可以看到為了達成「反轉」這件事情,我多宣告了一個 output 陣列(花到額外的空間來放),裡面總共有五格,所以看起來 reverseArr 的空間複雜度是 5?

感覺怪怪的對吧!因為這個 output 會根據 input 進來的參數大小,而有所不同,因此我們不能夠直接說空間複雜度是 5。

Big O notation(Big O 表示法)

我們使用 Big O notation,表達在「最壞情況下的複雜度等級」,如果像上例複雜度會隨著 input 線性變動的,會用 O(n) 來表示。

那如果不會隨著 input 變動的會像這樣:

const reverseArr = (input) => {
    let temp;
    const length = input.length;
    for(let i = 0; i<=length/2; i++) {
        temp = input[i];
        input[i] = input[length-i-1];
        input[length-i-1] = temp;
    }
    console.log(input);
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

執行結果

[5, 4, 3, 2, 1]

可以看到上面的寫法,同樣是為了達成「反轉」這件事情,但我都在 input 本體上面操作,完全沒有使用到額外的空間 output,也就是說,無論 inputlength 有多大,這個函式都不會花費更多空間,稱之為 O(1)

其中 1 其實是代表常數,並不是真的只花 1 個空間,而是表達不會隨著 input.length 變動

上面還有提到另一個重點是,Big O 代表的是「最壞情況」,會這樣說是因為執行一段程式所花費的時間或空間,有可能有三種情況:

  • 最佳情況
  • 平均情況
  • 最壞情況

比如說,我們要從陣列中找到一個元素,只要找到就可以不用繼續找了:

const findElement = (input, element) => {
    const length = input.length;
    for(let i = 0; i<length; i++) {
        if (input[i] === element) break;
    }
};

const arr = [1, 2, 3, 4, 5];
findElement(arr, 3);

像上面這種程式,執行 findElement(arr, 3) 只要跑三次迴圈就結束了,但如果執行 findElement(arr, 5) 就要跑五次迴圈(雖然這個範例的空間複雜度都是一樣的)。

因此我們會有上述三種情況,但計算機科學領域特別重視「上限」,才能夠確保系統能夠負荷最嚴重的狀況,所以我們才會只強調「最壞狀況」。

時間複雜度(Time complexity)

時間複雜度則是,我花了多少時間來完成這件事。

但這邊有一點要特別注意,並不是單純指花了幾分鐘來執行,因為每台電腦效能不一樣,我們不是要衡量哪一台電腦比較快,而是「不同的程式寫法在同一台電腦上執行」時的複雜度,因此我們會使用「執行了多少指令」來計算複雜度。

以剛剛上面的例子:

const reverseArr = (input) => {
    const output = []; // 1
    input.forEach(item => output.unshift(item)); // n
    console.log(output); // 1
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

可以看到我在註解的地方寫上了複雜度等級,總共合起來是 n+2,我們只取次方最高的 n,因為當 input 增加時,變化最大的會是最高次方的 n,所以 reverseArr 的時間複雜度就是 O(n)

時間與空間的權衡

可以看到剛剛同樣是一個「反轉」的任務:

  • 一個有宣告額外的空間 output
  • 一個沒有,但花費的程式碼變多

這代表時間與空間這兩種「效能」是 trade-off,很多時候如果要空間就得花時間,要時間就要花空間。

簡直跟租房子一樣,要大套房就要增加通勤時間

而這大多時候沒有正確答案,只取決於當下的需求,看是犧牲哪一邊比較恰當。(當然如果資料量根本不大,基本上電腦也不痛不癢)

這個網站很視覺化呈現了,不同複雜度執行起來的差異:

結語

演算法也是大學資工系基礎必修的一環,而且通常會跟資料結構相互配合,畢竟,使用怎樣的資料結構,會直接影響到演算法的複雜度,因此資料結構+演算法一起學,報個 2 次鐵人賽 60 天應該就可以了XD"

大多數人會覺得演算法很高深莫測,都是高手在用的,但其實經過今天的說明,不難看出其實,1+1 也是相加的一種演算法,演算法就只是達成目標所需的步驟而已。

之所以會看起來高大上,是因為如最後所說的,只有輸入資料量龐大的時候,才容易看出演算法好壞的落差,而會碰到龐大輸入量的,當然都是高手啦!

所以希望大家不要被「演算法」這個名字嚇到,去了解它,並且試著思考自己的程式是否有更好的演算法,即便資料量不大,也能夠在思考的過程中成長!

荊棘的路險峻
遠繞的路疲倦
在不知道是否存在的交會點
尋一處沙洲

參考資料

演算法 MDN
big O cheat sheet


上一篇
Day 24 - 資料結構入門理解
下一篇
Day 26 - Clean Code 邁向更好讀、好維護的程式
系列文
Javascript 從寫對到寫好30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言